//请你设计一个数据结构来高效管理网络路由器中的数据包。每个数据包包含以下属性： 
//
// 
// source：生成该数据包的机器的唯一标识符。 
// destination：目标机器的唯一标识符。 
// timestamp：该数据包到达路由器的时间戳。 
// 
//
// 实现 Router 类： 
//
// Router(int memoryLimit)：初始化路由器对象，并设置固定的内存限制。 
//
// 
// memoryLimit 是路由器在任意时间点可以存储的 最大 数据包数量。 
// 如果添加一个新数据包会超过这个限制，则必须移除 最旧的 数据包以腾出空间。 
// 
//
// bool addPacket(int source, int destination, int timestamp)：将具有给定属性的数据包添加到路由器。
// 
//
// 
// 如果路由器中已经存在一个具有相同 source、destination 和 timestamp 的数据包，则视为重复数据包。 
// 如果数据包成功添加（即不是重复数据包），返回 true；否则返回 false。 
// 
//
// int[] forwardPacket()：以 FIFO（先进先出）顺序转发下一个数据包。 
//
// 
// 从存储中移除该数据包。 
// 以数组 [source, destination, timestamp] 的形式返回该数据包。 
// 如果没有数据包可以转发，则返回空数组。 
// 
//
// int getCount(int destination, int startTime, int endTime)： 
//
// 
// 返回当前存储在路由器中（即尚未转发）的，且目标地址为指定 destination 且时间戳在范围 [startTime, endTime]（包括两端）内的
//数据包数量。 
// 
//
// 注意：对于 addPacket 的查询会按照 timestamp 的递增顺序进行。 
//
// 
//
// 示例 1： 
//
// 
// 输入： ["Router", "addPacket", "addPacket", "addPacket", "addPacket", 
//"addPacket", "forwardPacket", "addPacket", "getCount"] [[3], [1, 4, 90], [2, 5, 90], [1, 4
//, 90], [3, 5, 95], [4, 5, 105], [], [5, 2, 110], [5, 100, 110]] 
// 
//
// 输出： [null, true, true, false, true, true, [2, 5, 90], true, 1] 
//
// 解释： 
//Router router = new Router(3); // 初始化路由器，内存限制为 3。
// 
//router.addPacket(1, 4, 90); // 数据包被添加，返回 True。
// 
//router.addPacket(2, 5, 90); // 数据包被添加，返回 True。
// 
//router.addPacket(1, 4, 90); // 这是一个重复数据包，返回 False。
// 
//router.addPacket(3, 5, 95); // 数据包被添加，返回 True。
// 
//router.addPacket(4, 5, 105); // 数据包被添加，
//[1, 4, 90] 被移除，因为数据包数量超过限制，返回 True。
// 
//router.forwardPacket(); // 转发数据包 
//[2, 5, 90] 并将其从路由器中移除。
// 
//router.addPacket(5, 2, 110); // 数据包被添加，返回 True。
// 
//router.getCount(5, 100, 110); // 唯一目标地址为 5 且时间在 
//[100, 110] 范围内的数据包是 
//[4, 5, 105]，返回 1。
//
// 示例 2： 
//
// 
// 输入： ["Router", "addPacket", "forwardPacket", "forwardPacket"] [[2], [7, 4, 90
//], [], []] 
// 
//
// 输出： [null, true, [7, 4, 90], []] 
//
// 解释： 
//Router router = new Router(2); // 初始化路由器，内存限制为 2。
// 
//router.addPacket(7, 4, 90); // 返回 True。
// 
//router.forwardPacket(); // 返回 
//[7, 4, 90]。
// 
//router.forwardPacket(); // 没有数据包可以转发，返回 
//[]。
//
// 
//
// 提示： 
//
// 
// 2 <= memoryLimit <= 10⁵ 
// 1 <= source, destination <= 2 * 10⁵ 
// 1 <= timestamp <= 10⁹ 
// 1 <= startTime <= endTime <= 10⁹ 
// addPacket、forwardPacket 和 getCount 方法的总调用次数最多为 10⁵。 
// 对于 addPacket 的查询，timestamp 按递增顺序给出。 
// 
//
// Related Topics 设计 队列 数组 哈希表 二分查找 有序集合 👍 25 👎 0


package LeetCode.editor.cn;

import java.util.*;

/**
 * @author ldltd
 * @date 2025-09-21 17:08:24
 * @description 3508.设计路由器
 */
public class ImplementRouter{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 ImplementRouter fun=new ImplementRouter();

	 }

//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Router1 {
        int memoryLimit;
        List<int[]> packets; // 存储数据包的列表
        Set<String> packetSet; // 用于检查重复数据包的集合
    public Router1(int memoryLimit) {
        this.memoryLimit = memoryLimit;
        packets = new ArrayList<>();
        packetSet = new java.util.HashSet<>();
    }

    public boolean addPacket(int source, int destination, int timestamp) {
        // 检查是否有重复数据包
        if(packetSet.contains(source + "," + destination + "," + timestamp)) {
            return false; // 重复数据包，返回 false
        }

        // 如果内存已满，移除最旧的数据包
        if (packets.size() >= memoryLimit) {
            packets.remove(0); // 移除最旧的数据包
        }

        // 添加新数据包
        packets.add(new int[]{source, destination, timestamp});
        packetSet.add(source + "," + destination + "," + timestamp);
        return true; // 成功添加数据包，返回 true
    }

    public int[] forwardPacket() {
        if (packets.isEmpty()) {
            return new int[0]; // 没有数据包可以转发，返回空数组
        }

        // 转发最旧的数据包
        int[] packet = packets.remove(0);
        packetSet.remove(packet[0] + "," + packet[1] + "," + packet[2]);
        return packet; // 返回转发的数据包
    }

    public int getCount(int destination, int startTime, int endTime) {
        int count = 0;
        for (int[] packet : packets) {
            if (packet[1] == destination && packet[2] >= startTime && packet[2] <= endTime) {
                count++;
            }
        }
        return count; // 返回符合条件的数据包数量
    }
}
    class Router {
         // 最大内存限制
        private int lim;
        // 已存储的数据包的唯一标识
        private Set<Long> vis = new HashSet<>();
        // 存储数据包的队列
        private Deque<int[]> q = new ArrayDeque<>();
        // 记录每个目标地址已转发的数据包数量
        private Map<Integer, Integer> idx = new HashMap<>();
        // 记录每个目标地址对应的时间戳列表
        private Map<Integer, List<Integer>> d = new HashMap<>();

        public Router(int memoryLimit) {
            this.lim = memoryLimit;
        }

        public boolean addPacket(int source, int destination, int timestamp) {
            long x = f(source, destination, timestamp);
            // 检查是否为重复数据包
            if (vis.contains(x)) {
                return false;
            }
            // 添加数据包的唯一标识
            vis.add(x);
            // 如果内存已满，转发最旧的数据包
            if (q.size() >= lim) {
                forwardPacket();
            }
            // 添加新数据包到队列
            q.offer(new int[] {source, destination, timestamp});
            // 记录时间戳
            d.computeIfAbsent(destination, k -> new ArrayList<>()).add(timestamp);
            return true;
        }

        public int[] forwardPacket() {
            // 如果没有数据包可以转发，返回空数组
            if (q.isEmpty()) {
                return new int[] {};
            }
            // 转发最旧的数据包
            int[] packet = q.poll();
            // 移除数据包的唯一标识
            int s = packet[0], d_ = packet[1], t = packet[2];
            // 去重列表中移除该数据包
            vis.remove(f(s, d_, t));
            // 更新已转发的数据包数量
            idx.merge(d_, 1, Integer::sum);
            return new int[] {s, d_, t};
        }
        // 将三个整数编码为一个长整数，确保唯一性
        private long f(int a, int b, int c) {
            return ((long) a << 46) | ((long) b << 29) | (long) c;
        }

        public int getCount(int destination, int startTime, int endTime) {
            // 获取目标地址对应的时间戳列表
            List<Integer> ls = d.getOrDefault(destination, List.of());
            // 获取已转发的数据包数量
            int k = idx.getOrDefault(destination, 0);
            // 使用二分查找计算在时间范围内的数据包数量
            int i = lowerBound(ls, startTime, k);
            // 查找结束时间的下一个位置
            int j = lowerBound(ls, endTime + 1, k);
            return j - i;
        }

        private int lowerBound(List<Integer> list, int target, int fromIndex) {
            int l = fromIndex, r = list.size();
            while (l < r) {
                int m = (l + r) >>> 1;
                if (list.get(m) < target) {
                    l = m + 1;
                } else {
                    r = m;
                }
            }
            return l;
        }
    }
/**
 * Your Router object will be instantiated and called as such:
 * Router obj = new Router(memoryLimit);
 * boolean param_1 = obj.addPacket(source,destination,timestamp);
 * int[] param_2 = obj.forwardPacket();
 * int param_3 = obj.getCount(destination,startTime,endTime);
 */
//leetcode submit region end(Prohibit modification and deletion)

}
